import java.util.ArrayList;
import java.util.Arrays;

/**
 * 二分查找
 *
 * @Author: wanqian
 * @Date: 2021/2/26 10:38
 */
public class BinarySearchDemo {

    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214, 23, 77, 4, 5, 118, 45, 96, 1, 14, 14};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
//        int i = insetSearch(arr, 0, arr.length - 1, 14);
//        int i = binSearch(arr, 14);
        ArrayList<Integer> integers = binSearchList(arr, 14);
        System.out.println(integers);

//        System.out.println(i);
    }

    public static int binSearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (arr[mid] > target) {
                right = mid - 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static ArrayList<Integer> binSearchList(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (arr[mid] > target) {
                right = mid - 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                ArrayList<Integer> indexList = new ArrayList<>();
                indexList.add(mid);

                int index = mid;
                while (--index >= 0 && (arr[index] == target)) {
                    indexList.add(index);
                }

                index = mid;
                while (++index < arr.length && (arr[index] == target)) {
                    indexList.add(mid);
                }
                return indexList;
            }
        }
        return null;
    }

    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int mid = (left + right) / 2;
        while (left <= right) {
            if (target < arr[mid]) {
                right = mid - 1;
            } else if (target > arr[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
            mid = (left + right) / 2;
        }
        return -1;
    }

    public static int binSearchCruise(int[] arr, int left, int right, int target) {
        if (left > right || target > arr[right] || target < arr[left]) {
            return -1;
        }

        int mid = (right + left) / 2;
        if (arr[mid] < target) {
            return binSearchCruise(arr, mid + 1, right, target);
        } else if (arr[mid] > target) {
            return binSearchCruise(arr, left, mid - 1, target);
        } else {
            return mid;
        }
    }

    public static int insetSearch(int[] arr, int left, int right, int target) {
        if (left > right || target > arr[right] || target < arr[left]) {
            return -1;
        }

        int mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);
        if (arr[mid] < target) {
            return binSearchCruise(arr, mid + 1, right, target);
        } else if (arr[mid] > target) {
            return binSearchCruise(arr, left, mid - 1, target);
        } else {
            return mid;
        }
    }
}
